SherbyNet - /page/wikibook/entry.mu

Micron Document

Injective function

22.2 KB · ⇊ 14 parts · ⤓ Micron 22.2 KB · ⤓ HTML 215.3 KB

──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────

top

In mathematics, an injective function (also known as injection, or one-to-one functioncite-ref-1[1] ) is a function f that maps distinct elements of its domain to distinct elements of its codomain; that is, x1 ≠ x2 implies f(x1) ≠ f(x2) (equivalently by contraposition, f(x1) = f(x2) implies x1 = x2). In other words, every element of the function's codomain is the image of at most one element of its domain.cite-ref-0-2-0[2] The term one-to-one function must not be confused with one-to-one correspondence that refers to bijective functions, which are functions such that each element in the codomain is an image of exactly one element in the domain.

A homomorphism between algebraic structures is a function that is compatible with the operations of the structures. For all common algebraic structures, and, in particular for vector spaces, an injective homomorphism is also called a monomorphism. However, in the more general context of category theory, the definition of a monomorphism differs from that of an injective homomorphism.cite-ref-3[3] This is thus a theorem that they are equivalent for algebraic structures; see Homomorphism § Monomorphism for more details.

A function f {\displaystyle f} that is not injective is sometimes called many-to-one.cite-ref-0-2-1[2]

Contents

• Definition

• Examples

• Injections can be undone

• Injections may be made invertible

• Other properties

• Proving that functions are injective

• Gallery

• See also

• Notes

• References

• External links

Definition

Let f {\displaystyle f} be a function whose domain is a set X . {\displaystyle X.} The function f {\displaystyle f} is said to be injective provided that for all a {\displaystyle a} and b {\displaystyle b} in X , {\displaystyle X,} if f ( a ) = f ( b ) , {\displaystyle f(a)=f(b),} then a = b {\displaystyle a=b} ; that is, f ( a ) = f ( b ) {\displaystyle f(a)=f(b)} implies a = b . {\displaystyle a=b.} Equivalently, if a ≠ ≠ b , {\displaystyle a\neq b,} then f ( a ) ≠ ≠ f ( b ) {\displaystyle f(a)\neq f(b)} in the contrapositive statement.

Symbolically, ∀ ∀ a , b ∈ ∈ X , f ( a ) = f ( b ) ⇒ ⇒ a = b , {\displaystyle \forall a,b\in X,\;\;f(a)=f(b)\Rightarrow a=b,} which is logically equivalent to the contrapositive,cite-ref-4[4] ∀ ∀ a , b ∈ ∈ X , a ≠ ≠ b ⇒ ⇒ f ( a ) ≠ ≠ f ( b ) . {\displaystyle \forall a,b\in X,\;\;a\neq b\Rightarrow f(a)\neq f(b).} An injective function (or, more generally, a monomorphism) is often denoted by using the specialized arrows ↣ or ↪ (for example, f : A ↣ ↣ B {\displaystyle f:A\rightarrowtail B} or f : A ↪ ↪ B {\displaystyle f:A\hookrightarrow B} ), although some authors specifically reserve ↪ for an inclusion map.cite-ref-5[5]

Examples

For visual examples, readers are directed to the gallery section.

• For any set X {\displaystyle X} and any subset S ⊆ ⊆ X , {\displaystyle S\subseteq X,} the inclusion map S → → X {\displaystyle S\to X} (which sends any element s ∈ ∈ S {\displaystyle s\in S} to itself) is injective. In particular, the identity function X → → X {\displaystyle X\to X} is always injective (and in fact bijective).

• If the domain of a function is the empty set, then the function is the empty function, which is injective.

• If the domain of a function has one element (that is, it is a singleton set), then the function is always injective.

• The function f : R → → R {\displaystyle f:\mathbb {R} \to \mathbb {R} } defined by f ( x ) = 2 x + 1 {\displaystyle f(x)=2x+1} is injective.

• The function g : R → → R {\displaystyle g:\mathbb {R} \to \mathbb {R} } defined by g ( x ) = x 2 {\displaystyle g(x)=x^{2}} is not injective, because (for example) g ( 1 ) = 1 = g ( − − 1 ) . {\displaystyle g(1)=1=g(-1).} However, if g {\displaystyle g} is redefined so that its domain is the non-negative real numbers [0,+∞), then g {\displaystyle g} is injective.

• The exponential function exp : R → → R {\displaystyle \exp :\mathbb {R} \to \mathbb {R} } defined by exp ⁡ ⁡ ( x ) = e x {\displaystyle \exp(x)=e^{x}} is injective (but not surjective, as no real value maps to a negative number).

• The natural logarithm function ln : ( 0 , ∞ ∞ ) → → R {\displaystyle \ln :(0,\infty )\to \mathbb {R} } defined by x ↦ ↦ ln ⁡ ⁡ x {\displaystyle x\mapsto \ln x} is injective.

• The function g : R → → R {\displaystyle g:\mathbb {R} \to \mathbb {R} } defined by g ( x ) = x n − − x {\displaystyle g(x)=x^{n}-x} is not injective, since, for example, g ( 0 ) = g ( 1 ) = 0. {\displaystyle g(0)=g(1)=0.}

More generally, when X {\displaystyle X} and Y {\displaystyle Y} are both the real line R , {\displaystyle \mathbb {R} ,} then an injective function f : R → → R {\displaystyle f:\mathbb {R} \to \mathbb {R} } is one whose graph is never intersected by any horizontal line more than once. This principle is referred to as the horizontal line test.cite-ref-0-2-2[2]

Injections can be undone

Functions with left inverses are always injections. That is, given f : X → → Y , {\displaystyle f:X\to Y,} if there is a function g : Y → → X {\displaystyle g:Y\to X} such that for every x ∈ ∈ X {\displaystyle x\in X} , g ( f ( x ) ) = x {\displaystyle g(f(x))=x} , then f {\displaystyle f} is injective. The proof is that

f ( a ) = f ( b ) → → g ( f ( a ) ) = g ( f ( b ) ) → → a = b . {\displaystyle f(a)=f(b)\rightarrow g(f(a))=g(f(b))\rightarrow a=b.}

In this case, g {\displaystyle g} is called a retraction of f . {\displaystyle f.} Conversely, f {\displaystyle f} is called a section of g . {\displaystyle g.}

Conversely, every injection f {\displaystyle f} with a non-empty domain has a left inverse g {\displaystyle g} . It can be defined by choosing an element a {\displaystyle a} in the domain of f {\displaystyle f} and setting g ( y ) {\displaystyle g(y)} to the unique element of the pre-image f − − 1 [ y ] {\displaystyle f^{-1}[y]} (if it is non-empty) or to a {\displaystyle a} (otherwise).cite-ref-6[6]

The left inverse g {\displaystyle g} is not necessarily an inverse of f , {\displaystyle f,} because the composition in the other order, f ∘ ∘ g , {\displaystyle f\circ g,} may differ from the identity on Y . {\displaystyle Y.} In other words, an injective function can be "reversed" by a left inverse, but is not necessarily invertible, which requires that the function is bijective.

Injections may be made invertible

In fact, to turn an injective function f : X → → Y {\displaystyle f:X\to Y} into a bijective (hence invertible) function, it suffices to replace its codomain Y {\displaystyle Y} by its actual image J = f ( X ) . {\displaystyle J=f(X).} That is, let g : X → → J {\displaystyle g:X\to J} such that g ( x ) = f ( x ) {\displaystyle g(x)=f(x)} for all x ∈ ∈ X {\displaystyle x\in X} ; then g {\displaystyle g} is bijective. Indeed, f {\displaystyle f} can be factored as In J , Y ∘ ∘ g , {\displaystyle \operatorname {In} _{J,Y}\circ g,} where In J , Y {\displaystyle \operatorname {In} _{J,Y}} is the inclusion function from J {\displaystyle J} into Y . {\displaystyle Y.}

More generally, injective partial functions are called partial bijections.

Other properties

• If f {\displaystyle f} and g {\displaystyle g} are both injective then f ∘ ∘ g {\displaystyle f\circ g} is injective.

• If g ∘ ∘ f {\displaystyle g\circ f} is injective, then f {\displaystyle f} is injective (but g {\displaystyle g} need not be).

• f : X → → Y {\displaystyle f:X\to Y} is injective if and only if, given any functions g , {\displaystyle g,} h : W → → X {\displaystyle h:W\to X} whenever f ∘ ∘ g = f ∘ ∘ h , {\displaystyle f\circ g=f\circ h,} then g = h . {\displaystyle g=h.} In other words, injective functions are precisely the monomorphisms in the category Set of sets.

• If f : X → → Y {\displaystyle f:X\to Y} is injective and A {\displaystyle A} is a subset of X , {\displaystyle X,} then f − − 1 ( f ( A ) ) = A . {\displaystyle f^{-1}(f(A))=A.} Thus, A {\displaystyle A} can be recovered from its image f ( A ) . {\displaystyle f(A).}

• If f : X → → Y {\displaystyle f:X\to Y} is injective and A {\displaystyle A} and B {\displaystyle B} are both subsets of X , {\displaystyle X,} then f ( A ∩ ∩ B ) = f ( A ) ∩ ∩ f ( B ) . {\displaystyle f(A\cap B)=f(A)\cap f(B).}

• Every function h : W → → Y {\displaystyle h:W\to Y} can be decomposed as h = f ∘ ∘ g {\displaystyle h=f\circ g} for a suitable injection f {\displaystyle f} and surjection g . {\displaystyle g.} This decomposition is unique up to isomorphism, and f {\displaystyle f} may be thought of as the inclusion function of the range h ( W ) {\displaystyle h(W)} of h {\displaystyle h} as a subset of the codomain Y {\displaystyle Y} of h . {\displaystyle h.}

• If f : X → → Y {\displaystyle f:X\to Y} is an injective function, then Y {\displaystyle Y} has at least as many elements as X , {\displaystyle X,} in the sense of cardinal numbers. In particular, if, in addition, there is an injection from Y {\displaystyle Y} to X , {\displaystyle X,} then X {\displaystyle X} and Y {\displaystyle Y} have the same cardinal number. (This is known as the Cantor–Bernstein–Schroeder theorem.)

• If both X {\displaystyle X} and Y {\displaystyle Y} are finite with the same number of elements, then f : X → → Y {\displaystyle f:X\to Y} is injective if and only if f {\displaystyle f} is surjective (in which case f {\displaystyle f} is bijective).

• An injective function which is a homomorphism between two algebraic structures is an embedding.

• Unlike surjectivity, which is a relation between the graph of a function and its codomain, injectivity is a property of the graph of the function alone; that is, whether a function f {\displaystyle f} is injective can be decided by only considering the graph (and not the codomain) of f . {\displaystyle f.}

Proving that functions are injective

A proof that a function f {\displaystyle f} is injective depends on how the function is presented and what properties the function holds. For functions that are given by some formula there is a basic idea. We use the definition of injectivity, namely that if f ( x ) = f ( y ) , {\displaystyle f(x)=f(y),} then x = y . {\displaystyle x=y.} cite-ref-7[7]

Here is an example: f ( x ) = 2 x + 3 {\displaystyle f(x)=2x+3}

Proof: Let f : X → → Y . {\displaystyle f:X\to Y.} Suppose f ( x ) = f ( y ) . {\displaystyle f(x)=f(y).} So 2 x + 3 = 2 y + 3 {\displaystyle 2x+3=2y+3} implies 2 x = 2 y , {\displaystyle 2x=2y,} which implies x = y . {\displaystyle x=y.} Therefore, it follows from the definition that f {\displaystyle f} is injective.

There are multiple other methods of proving that a function is injective. For example, in calculus if f {\displaystyle f} is a differentiable function defined on some interval, then it is sufficient to show that the derivative is always positive or always negative on that interval. In linear algebra, if f {\displaystyle f} is a linear transformation it is sufficient to show that the kernel of f {\displaystyle f} contains only the zero vector. If f {\displaystyle f} is a function with finite domain it is sufficient to look through the list of images of each domain element and check that no image occurs twice on the list.

A graphical approach for a real-valued function f {\displaystyle f} of a real variable x {\displaystyle x} is the horizontal line test. If every horizontal line intersects the curve of f ( x ) {\displaystyle f(x)} in at most one point, then f {\displaystyle f} is injective or one-to-one.

Gallery